In communication between nodes in a local area network (LAN), communication devices, such as Layer (L) 2 switches, that relay the communication are used. The L2 switches have a Media Access Control (MAC) learning function in order to perform frame transfer.
Namely, if a switch that uses the MAC learning function receives a frame, the switch stores, in a table called a MAC learning table, the association relationship between the port that received the frame and the MAC address of the terminal that is the transmission source of the frame. If the switch receives a frame that is addressed to the MAC address stored in the MAC learning table from another port, the switch transfers the received frame from the port that is indicated that, in the MAC learning table, the learning has been completed.
Furthermore, if a lot of electronic devices are connected in a network, an amount of the processing load of the communication devices that provide a LAN service is increased. The increase in the processing load indicates that the number of entries to be controlled by the communication devices is increased.
When a communication device learns MAC addresses, the communication device often manages a MAC address table by using a ternary content addressable memory (TCAM) or a hash algorithm in order to speed up the processes.
If the TCAM is used, an advantage is provided in that the entry registration is certainly possible. However, the TCAM is expensive when compared with general purpose volatile devices and consumes a large amount of electrical power; therefore, the TCAM is unsuitable for the large amount of entry registration.
In contrast, with the communication devices that manage the MAC address table by using the hash algorithm, general purpose volatile memories can be used and thus the cost can be reduced. Furthermore, with such communication devices, because the MAC address table is degenerated by a hash expression, although a collision occurs in an entry, a large amount of entries can be managed with a small amount of resources.
Conventionally, if a collision occurs, a communication device deletes an already registered entry and then registers a new entry. If the already registered entry is deleted, it is difficult to perform the communication, which uses the MAC address table, with respect to the MAC address that is associated with the subject entry. This state may sometimes be referred to as “instantaneous interruption” of the already registered entry. Then, the communication device performs the Flooding. In this case, information is also sent to an unintended port. Because the Flooding is performed even if a Static MAC that is the MAC address that is intentionally registered by a user is used, there if a problem in that security is decreased.
Furthermore, as a management technology of MAC addresses by using the hash algorithm, for example, there is a conventional technology that divides a MAC address table into a plurality of banks and that registers an address that has been subjected to hash calculation in one of the banks. Furthermore, there is a conventional technology that performs, when an address that has been subjected to hash calculation is registered, the reordering if a location for the registration is not present.
Patent Document 1: Japanese Laid-open Patent Publication No. 2002-334114
Patent Document 2: Japanese National Publication of International Patent Application No. 2003-510963
However, even if the conventional technology that divides the MAC address table into the plurality of banks is used, because the same process as that used in the conventional technology is performed when a collision occurs, it is difficult to improve the probability that a new entry is registered in a free entry without deleting an already registered entry. Furthermore, even if the conventional technology that performs the reordering if a location for registration is not present due to a collision is used, there may possibly be a case in which, even if the reordering is performed, an address is not registered in a free entry. Thus, it is difficult to improve the probability that a new entry is registered in a free entry without deleting the already registered entry.